﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Numerics;

namespace Inspired.Euler
{
    /// <summary>
    /// Starting in the top left corner of a 22 grid, there are 6 routes (without backtracking) to the bottom right corner.
    /// 
    /// How many routes are there through a 2020 grid?
    /// </summary>
    public static class Problem015
    {
        /// <summary>
        /// Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?
        /// </summary>
        [EulerProblem(15, Title = "Starting in the top left corner in a 20 by 20 grid, how many routes are there to the bottom right corner?")]
        public static long Solve()
        {
            int n = 20; // http://en.wikipedia.org/wiki/Catalan_number
            return (long)((2 * n).Factorial() / ((n).Factorial() * (n).Factorial()));
        }
    }
}
